/* Compile with gcc -Wall -O3 -o as1_t2 as1_t2.c dummysort.c
   Then, start ./as1_t2
*/
#include "as1_t2.h"
#include <stdlib.h>
#include <stdio.h>

void print_task_ts(task_t** tasks, int cnt_tasks) {
	int i;
	printf("|");
	for (i = 0; i < cnt_tasks; i++) {
		printf("%4lu|", (*(tasks[i])).id);
	}
	printf("\n");
}

task_t** copyTask_tArray(task_t** tasks, int length) {
	task_t** result = malloc(sizeof(task_t) * length);
	int i;
	for (i = 0; i < length; i++) {
		result[i] = tasks[i];
	}
	return result;
}

void msort_merge(task_t** result, task_t** lefttasks, int cnt_left, task_t** righttasks, int cnt_right) {
	int idx_left;
	int idx_right;
	int idx_result;
	
	idx_left	= 0;
	idx_right	= 0;
	idx_result	= 0;
	
	// printf("%30s", "input of msort_merge: \n");
	// print_task_ts(lefttasks, cnt_left);
	// printf("&&\n");
	// print_task_ts(righttasks, cnt_right);
	
	while (idx_left + idx_right < cnt_left + cnt_right) {
		// printf("idx_left + idx_right = %d + %d = %d ?= %d\n", idx_left, idx_right, idx_left + idx_right, idx_result);
		// printf("left <-> right : [%d]=%5lu <-> [%d]=%5lu\n", idx_left, (*(lefttasks[idx_left])).id, idx_right, (*(righttasks[idx_right])).id);
		if (idx_right >= cnt_right || (idx_left < cnt_left && (*(lefttasks[idx_left])).id < (*(righttasks[idx_right])).id)) {
			// printf("left smaller->");
			result[idx_left + idx_right] = lefttasks[idx_left];
			// printf("NO ERROR\n");
			idx_left++;
		} else {
			// printf("right smaller->");
			result[idx_left + idx_right] = righttasks[idx_right];
			// printf("NO ERROR\n");
			idx_right++;
		}
		idx_result++;
	}
	
	
	// printf("%30s", "result of msort_merge: ");
	// print_task_ts(result, idx_left + idx_right);
}

void msort_helper(task_t** tasks, int count) {
	if (count <= 1) {
		return;
	} else {
		// print_task_ts(tasks, count);
		int leftcount	= count / 2;
		int rightcount	= count - leftcount;
		// print_task_ts(tasks, leftcount);
		// task_t** left	= msort_helper(tasks,				leftcount);
		task_t** left	= copyTask_tArray(tasks, leftcount);
		// print_task_ts(&(tasks[leftcount]),	rightcount);
		// task_t** right	= msort_helper(&(tasks[leftcount]),	rightcount);
		task_t** right	= copyTask_tArray(&(tasks[leftcount]), rightcount);
		msort_helper(left, leftcount);
		msort_helper(right, rightcount);
		msort_merge(tasks, left, leftcount, right, rightcount);
	}
}

void msort(task_t** tasks, int count){
	msort_helper(tasks, count);
}

/** Returns a pointer to an array of newly created tasks or NULL if it failed.
 * @param taskIds The ids for the to-be-created task_ts.
 * @param count The number of random tasks to be made.
 * @return task_t** Array of pointers to new task_ts.
 * @requires count != NULL
 */
/*/
task_t** makeTasks(unsigned long taskIds[], int count){
	task_t** tasks;
	int i;

	// Allocate memory or return NULL.
	tasks = (task_t**) malloc(sizeof(task_t*) * count);
	if (NULL == tasks) return NULL;
	
	// Give tasks an id
	for (i=0; i<count; ++i){
		tasks[i] = (task_t*) malloc(sizeof(task_t));
		// memset(tasks[i], 0x0, sizeof(task_t));
		tasks[i]->id = taskIds[i];
		// printf("%d :: %lu\n", i, tasks[i]->id);
	}
	
	return tasks;
}

int main(int argc, char** argv) {
	int count = 64;
	unsigned long to_sort_ids[64] = {5, 3, 1, 6, 2, 4, 7,345,56,6,45,3425,456,546,34,35,45,32,56,5,34,324,46,335,34,34,6,34,43,43,56,45,34,4,6,7,8,8,7,654,32,1,234,54,756,45,63425,47,678,67845,6,32443765,654,3426,754783,452,3457,657,3242,35676,80,967734,541,2345};
	// unsigned long to_sort_ids[0] = { };
	task_t** to_sort_tasks;
	task_t** sorted_tasks;
	to_sort_tasks = makeTasks(to_sort_ids, count);
	sorted_tasks = malloc(count * sizeof(task_t));
	
	// print_task_ts(to_sort_tasks, count);
	msort(to_sort_tasks, count);
	// printf("%30s", "result of msort: ");
	// print_task_ts(to_sort_tasks, count);
	
	return 0;
}

//*/
